#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

#define mpp pair<int, pair<int, int> >
#define mp(a,b,c) make_pair(a, make_pair(b,c))
#define INF 200000000

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

int dist[60][60];

class DungeonEscape {
public:
	int exitTime(vector <string>, vector <string>, vector <string>, vector <string>, int, int);
};

int DungeonEscape::exitTime(vector <string> up, vector <string> down, vector <string> east, vector <string> west, int sl, int se) {
	int N = up.size();
	int M = up[0].size();
	for(int i=0; i<N; i++) for(int j=0; j<M; j++) dist[i][j] = INF;
	
	priority_queue<mpp> q;
	q.push(mp(0, sl, se));
	while(!q.empty()){
		int x = q.top().second.first;
		int y = q.top().second.second;
		int cost = -q.top().first;
		q.pop();
		if(x <= -1) return cost;
		if(dist[x][y] <= cost) continue;
		if(x>=N || y<0 || y>=M || cost>=(N-x)*M) continue;
		dist[x][y] = cost;
		for(int i=0; i<4; i++){
			int c;
			if(i==0) c=east[x][y];
			if(i==1) c=west[x][y];
			if(i==2) c=down[x][y];
			if(i==3) c=up[x][y];
			c -= 48;
			if(c<0 || c>9) continue;
			q.push(mp(-cost-c, x+dx[i], y+dy[i]));
		}
	}
	return -1;
}


double test0() {
	string t0[] = {"0x4",
 "0x3",
 "0x3"};
	vector <string> p0(t0, t0+sizeof(t0)/sizeof(string));
	string t1[] = {"0x9",
 "009",
 "0x9"};
	vector <string> p1(t1, t1+sizeof(t1)/sizeof(string));
	string t2[] = {"0x9",
 "1x9",
 "009"};
	vector <string> p2(t2, t2+sizeof(t2)/sizeof(string));
	string t3[] = {"0x9",
 "0x0",
 "009"};
	vector <string> p3(t3, t3+sizeof(t3)/sizeof(string));
	int p4 = 2;
	int p5 = 2;
	DungeonEscape * obj = new DungeonEscape();
	clock_t start = clock();
	int my_answer = obj->exitTime(p0, p1, p2, p3, p4, p5);
	clock_t end = clock();
	delete obj;
	cout <<"Time: " <<(double)(end-start)/CLOCKS_PER_SEC <<" seconds" <<endl;
	int p6 = 10;
	cout <<"Desired answer: " <<endl;
	cout <<"\t" << p6 <<endl;
	cout <<"Your answer: " <<endl;
	cout <<"\t" << my_answer <<endl;
	if (p6 != my_answer) {
		cout <<"DOESN'T MATCH!!!!" <<endl <<endl;
		return -1;
	}
	else {
		cout <<"Match :-)" <<endl <<endl;
		return (double)(end-start)/CLOCKS_PER_SEC;
	}
}
double test1() {
	string t0[] = {"xxxxxxxxx1",
 "1xxxxxxxxx",
 "xxxxxxxxx1"};
	vector <string> p0(t0, t0+sizeof(t0)/sizeof(string));
	string t1[] = {"xxxxxxxxxx",
 "xxxxxxxxxx",
 "xxxxxxxxxx"};
	vector <string> p1(t1, t1+sizeof(t1)/sizeof(string));
	string t2[] = {"1111111111",
 "xxxxxxxxxx",
 "1111111111"};
	vector <string> p2(t2, t2+sizeof(t2)/sizeof(string));
	string t3[] = {"xxxxxxxxxx",
 "1111111111",
 "xxxxxxxxxx"};
	vector <string> p3(t3, t3+sizeof(t3)/sizeof(string));
	int p4 = 2;
	int p5 = 0;
	DungeonEscape * obj = new DungeonEscape();
	clock_t start = clock();
	int my_answer = obj->exitTime(p0, p1, p2, p3, p4, p5);
	clock_t end = clock();
	delete obj;
	cout <<"Time: " <<(double)(end-start)/CLOCKS_PER_SEC <<" seconds" <<endl;
	int p6 = 30;
	cout <<"Desired answer: " <<endl;
	cout <<"\t" << p6 <<endl;
	cout <<"Your answer: " <<endl;
	cout <<"\t" << my_answer <<endl;
	if (p6 != my_answer) {
		cout <<"DOESN'T MATCH!!!!" <<endl <<endl;
		return -1;
	}
	else {
		cout <<"Match :-)" <<endl <<endl;
		return (double)(end-start)/CLOCKS_PER_SEC;
	}
}
double test2() {
	string t0[] = {"xxxxxxxxx1",
 "xxxx999991",
 "x999999991"};
	vector <string> p0(t0, t0+sizeof(t0)/sizeof(string));
	string t1[] = {"1111111111",
 "1111111111",
 "1111111111"};
	vector <string> p1(t1, t1+sizeof(t1)/sizeof(string));
	string t2[] = {"1111122242",
 "2222222241",
 "2111111111"};
	vector <string> p2(t2, t2+sizeof(t2)/sizeof(string));
	string t3[] = {"xxxxxxxxx1",
 "1111111111",
 "xxxxxxxxx1"};
	vector <string> p3(t3, t3+sizeof(t3)/sizeof(string));
	int p4 = 2;
	int p5 = 0;
	DungeonEscape * obj = new DungeonEscape();
	clock_t start = clock();
	int my_answer = obj->exitTime(p0, p1, p2, p3, p4, p5);
	clock_t end = clock();
	delete obj;
	cout <<"Time: " <<(double)(end-start)/CLOCKS_PER_SEC <<" seconds" <<endl;
	int p6 = -1;
	cout <<"Desired answer: " <<endl;
	cout <<"\t" << p6 <<endl;
	cout <<"Your answer: " <<endl;
	cout <<"\t" << my_answer <<endl;
	if (p6 != my_answer) {
		cout <<"DOESN'T MATCH!!!!" <<endl <<endl;
		return -1;
	}
	else {
		cout <<"Match :-)" <<endl <<endl;
		return (double)(end-start)/CLOCKS_PER_SEC;
	}
}
double test3() {
	string t0[] = {"1x2x3x4x5x6x7x8x9",
 "00000000000000000",
 "98765432223456789",
 "12345678987654321"};
	vector <string> p0(t0, t0+sizeof(t0)/sizeof(string));
	string t1[] = {"00000000000000000",
 "00000000000000000",
 "00000000000000000",
 "00000000000000000"};
	vector <string> p1(t1, t1+sizeof(t1)/sizeof(string));
	string t2[] = {"xxxxxxxxxxxxxxxxx",
 "xxxxxxxxxxxxxxxxx",
 "22222222222222222",
 "33333333333333333"};
	vector <string> p2(t2, t2+sizeof(t2)/sizeof(string));
	string t3[] = {"xxxxxxxxxxxxxxxxx",
 "xxxxxxxxxxxxxxxxx",
 "22222222222222222",
 "33333333333333333"};
	vector <string> p3(t3, t3+sizeof(t3)/sizeof(string));
	int p4 = 3;
	int p5 = 12;
	DungeonEscape * obj = new DungeonEscape();
	clock_t start = clock();
	int my_answer = obj->exitTime(p0, p1, p2, p3, p4, p5);
	clock_t end = clock();
	delete obj;
	cout <<"Time: " <<(double)(end-start)/CLOCKS_PER_SEC <<" seconds" <<endl;
	int p6 = 17;
	cout <<"Desired answer: " <<endl;
	cout <<"\t" << p6 <<endl;
	cout <<"Your answer: " <<endl;
	cout <<"\t" << my_answer <<endl;
	if (p6 != my_answer) {
		cout <<"DOESN'T MATCH!!!!" <<endl <<endl;
		return -1;
	}
	else {
		cout <<"Match :-)" <<endl <<endl;
		return (double)(end-start)/CLOCKS_PER_SEC;
	}
}

int main() {
	int time;
	bool errors = false;
	
	time = test0();
	if (time < 0)
		errors = true;
	
	time = test1();
	if (time < 0)
		errors = true;
	
	time = test2();
	if (time < 0)
		errors = true;
	
	time = test3();
	if (time < 0)
		errors = true;
	
	if (!errors)
		cout <<"You're a stud (at least on the example cases)!" <<endl;
	else
		cout <<"Some of the test cases had errors." <<endl;
}

//Powered by [KawigiEdit] 2.0!
